class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}
public class detectCycletwo {
    /**
     * 环形链表2，中等题目
     * 给定一个链表的头节点，需要判断返回链表开始入环的第一个节点，如果链表无环则直接返回null
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
     * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     *
     * 不允许修改 链表
     */
    /**
     * 方法是双指针判断是否存在环，再在入口位置继续标记统计
     * @param head
     * @return
     */
    public static ListNode method(ListNode head){
        // 注意返回的是第一个环中的节点，这里需要记录的操作
        // 依旧采用的是双指针的解法
        ListNode slow = head;
        ListNode fast = head;
        // 结束条件是快指针不为空
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                // 说明此时存在环
                // 重新定义节点，用于判断重合的位置入环的第一个节点等
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头开始进行遍历相遇，每个都各自走一步直到相遇
                while(index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

    public static void main(String[] args) {

    }
}
